Description of the Related Art
The reproduction of color images is a problem of great importance in business, scientific and industrial applications. A comprehensive overview of this problem can be found in Hunt, R. E. G. (1987). The Reproduction of Color in Photography, Printing and Television. Fountain Press, England. Different areas, and a great diversity of applications, lead to the necessity of using different media in the color reproduction process: film, paper, monitor screens, video, etc. The present invention is concerned with the reproduction of color images on paper.
There are different graphical devices that are capable of reproducing images on different types of paper. Dye sublimation printing technology produces continuous tone images on photographic quality paper. Wax transfer, inkjet and laser printers are able to reproduce color on a wide diversity of papers. In the printing industry, the offset printing process is capable of reproducing images of high quality on plain paper. The offset process surpasses the existing digital color reproduction techniques having the benefits of greater flexibility, lower cost, higher quality, and greater printing volume.
Digital techniques have been introduced into the offset printing pipeline with the objective of reducing the costs and guaranteeing a better quality control. A complete account on the problems of using digital techniques on the offset printing pipeland can be found in Stone, M. C., Cowan, W. B., and Beatty, J. C. (1988). Color gamut mapping and the printing of digital color images. ACM Transactions on Graphics, 7(3).
The present invention is directed to a new halftoning technique for color reproduction. The method adapts to a wide range of color reproduction processes that use halftoning in order to account for the elimination of quantization contours: inkjet printers, laser printers, wax transfer printers and the offset color printing process. We focus the applications and examples of the method of low cost color inkjet printers, and on high resolution phototypesetters.
We should point out that in spite of the advances in the area of continuous tone digital printing technology (e.g., dye sublimation printers), halftoning techniques for color printing still have a long way to evolve. This technology is essential for the color printing industry, because of the adequacy of the offset printing process to rapidly reproduce colors with great flexibility, and low cost. Also, halftoning techniques will continue to be used on a wide range of color reproduction devices (inkjet printers, laser printers, wax transfer printers, etc.).
Color Separation and Halftoning
Color printing is based on a reflective light process. The ink of the paper modulates the wavelength of the incident light, and as a result, a different color is reflected from the inked paper. This process is similar to the generation of color using a subtractive system: as we add different colors to the paper, light of different wavelength will be reflected, producing a great diversity of new colors.
Theoretically, by combining the three primary colors Cyan (C), Magenta (M), and Yellow (Y) to emulate a subtractive color system, we could be able to reproduce on paper a wide gamut of colors. Nevertheless, several considerations, of different nature, support the necessity of using Black (K), as an additional color in the printing process (see Stone, Cowan and Beatty, 1988 or Yule, J. A. C. (1967). Principles of Color Reproduction. John Wiley and Sons, New York.)
The process of taking a color digital image and transforming its color space to the C M Y K color space, is called color separation. Since, at least theoretically, we are able to generate the black component from the C M Y primaries, we face the problem of trading off between C M Y and K values in the color separation process. The literature about this topic is abundant. The interested reader should consult Stone, Cowan and Beatty, 1988 for a good overview, or Molla, R. K. (1988). Electronic Color Separation. RK Printing and Publishing Company, West Virginia, USA, for a more comprehensive discussion of the problem.
FIG. 1 shows a printed color image, and FIG. 2 shows the contents of each of its C M Y K channels. FIG. 1 is essentially obtained by overprinting each of the C M Y K channels in FIG. 2. We will return to this overprinting process later on. For the moment, we should make an important remark: in order to print each of the channels C M Y K, we must quantize it to a bitmap image. There is, thus, the necessity of using halftoning techniques (see Ulichney, R. (1987). Digital Halftoning. MIT Press, Cambridge, Mass.) in the quantization of each C M Y K channel, after the color separation process. Halftoning techniques avoid the perception of the severe contouring artifacts produced by the 1-bit quantization process.
A simplified diagram of the pipeline is shown in FIG. 3. A more detailed diagram of this pipeline can be found in Stone, Cowan and Beatty, 1988.
The necessity of using halftoning techniques for color reproduction on paper, resulted into a halftoning carpentry. Indeed, a lot of publications and patents have appeared about digital halftoning algorithms for color printing.
Halftoning Methods
The display of continuous-tone images in bi-level devices implies in the quatization of its intensities to one of two levels. Before the introduction of digital techniques, halftoning was produced by an analog process. In this process, the grayscale image is photographed, using a high contrast film, through a very fine and uniform screen, originating an image formed by tiny black dots, whose size varies according to the gray level intensity of the original photograph.
Digital halftoning techniques are called dithering. This is an extreme case of discretization in which continuous intensity values must be converted into a discrete set of values (in this case, only two). This operation may cause a loss of information which is estimated by the guantization error. At a particular image element, this error is the difference between the continuous and discrete values. For a region R (i,j), i=1, . . . ,m, j=1, . . . ,n, of the image domain, we define the average intensity of the grayscale levels by ##EQU1## where .vertline.R(i,j)).vertline. is the number of pixels in R. The quantization error on R is the different between the average I.sub.m, and the average of the quantized pixels within the region.
Dithering techniques use a trade-off between spatial and tonal resolution. As the quantization error is spread over larger areas of the image, more tones can be represented. Gray levels are rendered in this way as patterns of black and white pixels. On the other hand, if dithering avoids contouring artifacts, it eliminates at the same time high frequency information contained in the image. The process also transforms true intensity boundaries into patterning features. In summary, intensity variation is displayed at the cost of poorer rendition of fine details. Good dithering techniques provide an optimal trade-off between tonal values and the rendition of image details.
Screening Methods for Color Halftoning
Dithering techniques can be classified according to the nature of patterns they generate, and also the type of pixel configuration they produce. These two classification criteria capture the main features of the textures created to represent low frequency areas of the image, and also, to get a better rendition of the image high frequencies.
Textures can be rendered by periodic or aperiodic patterns. In general, periodic patterns are generated by a deterministic process based on regular sampling of grids, and aperiodic patterns are modeled as stochastic processes.
The type of pixel configuration produced by dithering algorithms is determined by the spatial configuration of the "on" and "off" state of the image elements. Dispersed dot methods simulate grayscale areas by distributing the pixels, while clustered dot methods concentrate the dots in small groups.
Dot clustering techniques try to mimic the traditional analog halftoning technique used by the printing industry. The dispersed dithering method performs the halftoning in a way similar to some traditional pen-and-ink illustration techniques.
Clustered-dot dithering techniques are, in general, based on the ordered dither method, Ulichney, 1987. They distribute the black and white dot patterns (clusters) periodically, using a regular screen. There are some methods in the literature that are clustering without distributing them over a regular screen. Examples of these methods are found in Velho, L. and Gomes, J. (1991). Digital halftoning with space filling cures. Computer Graphics (Proceedings SIGGRAPH '91), 25(4):81-90 and Allebach, J. P. (1976). Random quasi-periodic halftone process. J. Opt. Soc. A.m., 66:909-917.
Most of the dispersed dot dithering techniques attain the dispersion of the image elements by diffusing the quantization error along neighbor regions. This process turns out to introduce a correlated noise in the spatial distribution of the black and white pixels. In general, the noise patterns are referred to as producing a stochastic screen. Good results are obtained using a correlated noise such that its spectrum lacks low frequency power. This noise is referred to as blue noise in the literature (Ulichney, 1987). We should observe that some dispersed dot dithering techniques use a regular, periodic screen. The classical example is the dispersed ordered dithering technique introduced by Bayer, B. E. (1973). An optimum method for two-level rendition of continuous-tone pictures. In International Conference on Communications, Conference Record, pages (26-11)-(26-15).
The wide range of dithering techniques cover many different applications and are suited for color reproduction on a great diversity of display devices. FIG. 4 summarizes the above review. The space filling curve dithering algorithm published in Velho and Gomes, 1991 uses clusters, but it performs a diffusion of the quantization error between neighbor clusters along the space filling curve. This justifies its position on the diagram in FIG. 4.
Regular Screening
Traditional screening methods, either analog or digital, obtain a dithered image by creating regular clusters of points. The black and white dot patterns inside the clusters have a variable size, according to the image tonal values. For this reason, these techniques are known by the name of amplitude modulated dithering technique, or simply A M dithering.
When this method is used, a halftoned image of each of the separated C M Y K channels is created. During the halftoning process, the cluster grids are conveniently rotated in order to avoid full overprinting of the clusters from each of the C M Y K channels. This is illustrated in FIG. 5 where we show an amplification of a detail of the image printed in FIG. 1.
The spatial distribution of the halftoning clusters on a regular screen is prone to producing moiree artifacts in the overprinting of the C M Y K channels. Moiree patterns are illustrated in FIG. 6. On the top, we show a grayscale synthetic image that resembles the texture pattern of a cloth. In the middle, we show a 1-bit, halftoned, version of the image, using a regular screen with an angle of 6.degree.. At the bottom, we show another halftoned version using a screen of 5.degree.. Moiree patterns are quite noticeable, especially on the image at the bottom. Detailed discussion of moiree patterns can be found in Amidror, I. (1991). The moiree phenomenon in color separation. In Raster Imaging and Digital Typography II, Proceedings of the 2nd Int. Conf. Raster Imaging and Digital Typography, volume 6, pages 98-119 and Amidror, I., Hersch, R., and Ostromoukhov, V. (1994). Spectral analysis and minimization of moiree patterns in color separation. Journal of Electronic Imaging, 3(3):295-317.
Stochastic Screening
The first attempt to avoid the perception of quantization contours was done in Roberts, L. G. (1962). Picture coding using pseudo-random noise. IRE Trans. Infor. Theory, IT-8:145-154. In this paper, the use of white noise to decorrelate the quantization error was introduced. It is for this reason that dithering techniques that use regular patterns of clusters are known by the name of ordered dithering.
The idea of using noise to decorrelate the quantization error, and to avoid the perception of the quantization contours is in the right direction. The problem with white noise is that it is completely uncorrelated and, therefore, it destroys all of the image high frequencies.
Dispersed dithering algorithms use a fixed point size and modulate the spatial distribution of black and white points to render the tonal values of the image. In contrast to AM dithering techniques, these algorithms are called frequency modulated dithering, or simply FM dithering. FM dithering techniques have been introduced recently in the raster image processor of high resolution phototypesetters.
The use of correlated noise to distribute spatially the black and white dots over the image domain, is quite opposite to techniques that use a regular screen for the spatial distribution of the dot patterns. For this reason, noise correlated dithering techniques are also known by the name of stochastic screen halftoning.
Since FM dithering techniques do not use clustering, they do not perform well on printing devices which do not have a very good precision in the dot size and positioning. In this paper, we will set forth a method that encompasses the characteristics from FM and AM dithering techniques. Specifically, the method of the present invention combines the following:
it uses clustering; PA1 it performs error diffusion; PA1 it uses stochastic screening. PA1 continuity: two consecutive pixels along the path of the space filling curve are in the same 4-connected neighborhood; PA1 non-directionality: in general, three consecutive pixels along the space filling curve path are not aligned. PA1 subdivide the image domain into cells; PA1 compute the average image intensity inside each cell; PA1 generate a black and white dot pattern with the cell average intensity; and PA1 position the dot pattern inside the cell to generate the cluster. PA1 an image cell with 16 elements; PA1 a dot pattern with 5 elements that represents the average intensity within the cell; PA1 the cell element with the highest black intensity level (in gray); PA1 the translation of the dot pattern center to the position of the highest black intensity level element of the cell.
Besides the above properties, the method provides for changing the cluster size according to the rate of change of the image color intensities.
One of the main advantage of FM dithering techniques resides in the fact that it does not use regular screens. This avoids the classical problem of moiree e patterns in the color printing process with halftoning techniques.
Stochastic Screening with SFC
In this section, we briefly review the dithering with space filling curves (SFC) published by Velho and Gomes, 1991. The method takes advantage of the characteristics of space filling curves to perform neighborhood operations essential to the spatial dithering process. The path of a space filling curve approximation is used to scan the image, generating a parametrization of the image elements satisfying two properties:
We observe that the traditional scanline traversal of the image elements has an exaggerated horizontal directionality and does not have continuity. The dithering method with space filling curves consists of four steps:
The subdivision of the image domain into cells is performed by following the path of the space filling curve until the number of elements visited is equal to the cell size. FIG. 7(a) shows part of the path of a Hilbert space filling curve, and a cell with 4.times.4 pixels. FIG. 7(b) shows 4.times.4 clusters with intensities varying from 15/16, on the upper left corner, to 0, on the lower right corner.
The last step of the algorithm positions the black and white dot pattern within the cell to generate the cluster. The choice we take consists in positioning the central pixel of the black pattern at the pixel inside the cell which has the highest black intensity level. This is illustrated in FIG. 8(a) for the 1-dimensional case, and in FIG. 8(b), for the 2-dimensional case. Each of these figures shows (from top to bottom):
This positioning method results in a cluster that provides a much better rendition of the image details, without sacrificing the low frequency textures.
We should observe that besides the non-directionality implied by the space filling curve traversal, the method used above to construct the cluster introduces a randomness to the distribution of the clusters over the image domain. Also, it is important to mention that the quantization error in a cell is propagated to the neighbor cell, along the path of the space filling curve. This characterizes the method as a clustered-dot dithering with stochastic screening technique.
In brief, the dithering method with space filling curves uses clustering similar to the traditional amplitude modulated (AM) techniques, but at the same time, it performs error diffusion, and disperses the clusters along the path of the space filling curve. Therefore, it incorporates characteristics of FM dithering techniques.